package sorting;

import java.util.ArrayList;
import java.util.List;

/**
 * Time Complexity: O(n*k), where n=array.size, and k=maxDigits
 * Space Complexity: O(n+k)
 */
public class RadixSort {

    public void radixSort(int array[], int maxDigits) {
        int exp = 1;//10^0;
        // create 10 buckets
        List<List<Integer>> bucketList = new ArrayList<>(10);
        // create list of results for each bucket
        for (int k = 0; k < 10; k++) {
            bucketList.add(new ArrayList<>());
        }
        for (int i = 0; i < maxDigits; i++) {
            // add values to bucket according to current digit
            for (int anArr : array) {
                int number = (anArr / exp) % 10;
                bucketList.get(number).add(anArr);
            }
            int index = 0;
            // chain values according to current bucket ordering (LSB to MSB)
            for (int k = 0; k < 10; k++) {
                for (int num : bucketList.get(k)) {
                    array[index] = num;
                    index++;
                }
                // prepare bucket for next round
                bucketList.get(k).clear();
            }
            exp *= 10; // switch to next digit
        }

        System.out.println("Sorted numbers");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ", ");
        }
    }

    public static void main(String[] argv) {
        int n = 5;
        int arr[] = {1, 4, 2, 3, 5, 10, 8};
        new RadixSort().radixSort(arr, 2);
    }
}

